package solution;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

/*
* 239
* */
public class MaxSlidingWindow {
    /*
    * 使用队列存数组下标，滑动一次比较
    * */
    public int[] sulution1(int[] nums, int k) {
        if (nums == null || k <= 0) {
            return new int[0];
        }
        int n = nums.length;
        int[] r = new int[n-k+1];
        int ri = 0;
        // store index
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < nums.length; i++) {
            // remove numbers out of range k
            while (!q.isEmpty() && q.peek() < i - k + 1) {
                q.poll();
            }
            // remove smaller numbers in k range as they are useless
            while (!q.isEmpty() && nums[q.peekLast()] < nums[i]) {
                q.pollLast();
            }
            // q contains index... r contains content
            q.offer(i);
            if (i >= k - 1) {
                r[ri++] = nums[q.peek()];
            }
        }
        return r;
    }

    /*
    * 使用队列
    * */
    public int[] sulution2(int[] nums, int k) {
        int n = nums.length;
        Deque<Integer> deque = new LinkedList<>();
        //先判断第一组的大小
        for (int i = 0 ; i < k ; i++){
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]){
                deque.pollLast();
            }
            deque.offerLast(i);
        }

        int[] ans = new int[n - k + 1];
        ans[0] = nums[deque.peekFirst()];
        for (int i = k ; i < n ; i++){
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]){
                deque.pollLast();
            }
            deque.offerLast(i);
            //检查鲜活度
            while (deque.peekFirst() <= i - k){
                deque.pollFirst();
            }
            ans[i - k + 1] = nums[deque.peekFirst()];
        }
        return ans;
    }

    /*
    * 暴力求解
    * 过不了测试
    * */
    public int[] sulution3(int[] nums, int k) {
        if (nums == null || nums.length == 0)
            return new int[0];
        int res[] = new int[nums.length - k + 1];
        for (int i = 0; i < res.length; i++) {
            int max = nums[i];
            //在每个窗口内找到最大值
            for (int j = 1; j < k; j++) {
                max = Math.max(max, nums[i + j]);
            }
            res[i] = max;
        }
        return res;
    }


    /*
    * 对数组两端扫描
    *
    * */
    public int[] sulution4(int[] nums, int k) {
        int len = nums.length;
        int[] maxLeft = new int[len];
        int[] maxRight = new int[len];
        //从左往右窗口的第一个最大值默认是数组第一个值
        maxLeft[0] = nums[0];
        //从右往左窗口的最后一个最大值是数组的最后一个值
        maxRight[len - 1] = nums[len - 1];

        for (int i = 1; i < len; i++) {
            //这里分别计算从前往后窗口的最大值和从后往前窗口的最大值。要搞懂这里的判断，如果
            //i % k == 0，表示到了下一个窗口
            maxLeft[i] = (i % k == 0) ? nums[i] : Math.max(maxLeft[i - 1], nums[i]);
            int j = len - i - 1;
            maxRight[j] = ((j + 1) % k == 0) ? nums[j] : Math.max(maxRight[j + 1], nums[j]);
        }
        //返回的结果值
        int[] res = new int[len - k + 1];
        for (int i = 0, j = 0; i < res.length; i++) {
            //取每个窗口内从左往右扫描的最后一个值和从右往左扫描的最后
            //一个值(如果从左边数是第一个)的最大值
            res[j++] = Math.max(maxRight[i], maxLeft[i + k - 1]);
        }
        return res;
    }
}
